home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr49 / 288_01.zip / TSP.C < prev    next >
Text File  |  1993-04-01  |  12KB  |  308 lines
  1. /*
  2.         HEADER:         CUG000.08;
  3.         TITLE:          TSP (main), ArcCost, Terminate, PrintCircuit,
  4.                         CalculateImprovements, PrintImprovement;
  5.         DATE:           Mar 89;
  6.         DESCRIPTION:    Traveling Salesman Problem Driver;
  7.         VERSION:        2.0;
  8.         FILENAME:       TSP.C;
  9.         SEE-ALSO:       NN.C, POPT.C, 2OPT.C, HYBRID.C, 3OPT.C, FN.C,
  10.                         BOOLEAN.H, NODELIST.H, TSP.H,
  11.                         BLDMTX.C, PRTMTX.C, TIME.C;
  12.         AUTHORS:        Kevin E. Knauss;
  13. */
  14.  
  15. #include <stdio.h>
  16. #include <nodelist.h>
  17. #include <tsp.h>
  18.  
  19. unsigned Network[MAXROWS][MAXCOLS];
  20.  
  21. /* This version of ArcCost to be used with complete matricies */
  22. unsigned ArcCost (FromIndex, ToIndex)
  23.    unsigned FromIndex, ToIndex;
  24. {
  25.    extern unsigned Network[MAXROWS][MAXCOLS];
  26.  
  27.    return (Network [FromIndex][ToIndex]);
  28. } /* ArcCost */
  29.  
  30.  
  31. main ()
  32. {
  33.    extern unsigned Network[MAXROWS][MAXCOLS];
  34.    char Names[MAXROWS][MAXLINE];
  35.    NODE *Path, *Path2, *DuplicatePath;
  36.    long CircuitCost, OrigCost;
  37.    unsigned NumberOfVirteces;
  38.    unsigned index;
  39.    unsigned FirstIndex, SecondIndex;
  40.    long NearNeighbor(), PointOpt(), TwoOpt(), Hybrid(), ThreeOpt();
  41.    long FarNeighbor();
  42.    char filename[MAXLINE], ValueString[MAXLINE];
  43.    long atol();
  44.    long StartTime, TotalTime, GetTime() , ElapsedTime();
  45.    FILE *fp;
  46.  
  47.    /* Input network to be traversed */
  48.       printf("\n\n\n****************************************");
  49.       printf("\n\nInput filename for input: ");
  50.       if (gets(filename) == NULL)
  51.          Terminate (-1, "   Execution Terminated At User Request!");
  52.       printf("\n   Reading distance matrix ... ");
  53.       StartTime = GetTime ();
  54.       if ((fp = fopen (filename, "r")) == NULL)
  55.          Terminate (-1, "   Execution Terminated - Invalid Open!");
  56.       fscanf (fp, "%u", &NumberOfVirteces);
  57.       for ( index = 1; index <= NumberOfVirteces; index++)
  58.          fscanf (fp, "%s", Names [index]);
  59.       for ( FirstIndex = 1; FirstIndex <= NumberOfVirteces; FirstIndex++)
  60.          for ( SecondIndex = 1; SecondIndex <= NumberOfVirteces;
  61.                                                            SecondIndex++) {
  62.             fscanf (fp, "%s", ValueString);
  63.             Network [FirstIndex][SecondIndex] = (unsigned) atol(ValueString);
  64.          }
  65.       fclose (fp);
  66.       TotalTime = ElapsedTime (StartTime);
  67.       printf("%ld ticks.", TotalTime);
  68.    /* Open output and print headers */
  69.       printf("\n\n\n****************************************");
  70.       printf("\n\nInput filename for output: ");
  71.       if (gets(filename) == NULL)
  72.          Terminate (-1, "   Execution Terminated At User Request!");
  73.       if (filename == "stdout")
  74.          fp = stdout;
  75.       else
  76.          if ((fp = fopen (filename, "w")) == NULL)
  77.             Terminate (-1, "   Execution Terminated - Invalid Open!");
  78.       fprintf(fp, "\n          ");
  79.       fprintf(fp, "T R A V E L I N G   S A L E S M A N   P R O B L E M");
  80.       fprintf(fp, "\n\n\nThe following results were produced for the");
  81.       fprintf(fp, " %u city problem:\n\n\n", NumberOfVirteces);
  82.       fprintf(fp, "Distance matrix was input in %ld ticks.\n\n\n", TotalTime);
  83.    /* Calculate and print initial solution - good starting circuit */
  84.       if ((Path = calloc (1, sizeof(NODE))) == NULL)
  85.          Terminate (-1, "Execution Terminated - Insuficient Memory!");
  86.       printf("\n   Nearhest Neighbor calculation ... ");
  87.       StartTime = GetTime ();
  88.       CircuitCost = NearNeighbor (NumberOfVirteces, Path);
  89.       TotalTime = ElapsedTime (StartTime);
  90.       printf("%ld ticks.", TotalTime);
  91.       fprintf(fp, "Nearest Neighbor solution: \n\n");
  92.       fprintf(fp, "   A circuit with cost %ld", CircuitCost);
  93.       fprintf(fp, " was found in %ld", TotalTime);
  94.       fprintf(fp, " ticks with the following path:\n   ");
  95.       PrintCircuit (fp, NumberOfVirteces, Path);
  96.       fprintf(fp, "\n\n\n");
  97.       OrigCost = CircuitCost;
  98.       if ((DuplicatePath = calloc (1, sizeof(NODE))) == NULL)
  99.          Terminate (-1, "Execution Terminated - Insuficient Memory!");
  100.       Path2 = DuplicatePath;
  101.       Path2->position = Path->position;
  102.       Path = Path->next;
  103.       while (Path->position != DuplicatePath->position) {
  104.          if ((Path2->next = calloc (1, sizeof(NODE))) == NULL)
  105.             Terminate (-1, "Execution Terminated - Insuficient Memory!");
  106.          Path2->next->prior = Path2;
  107.          Path2 = Path2->next;
  108.          Path2->position = Path->position;
  109.          Path = Path->next;
  110.       }
  111.       DuplicatePath->prior = Path2;
  112.       Path2->next = DuplicatePath;
  113.       CalculateImprovements (fp, NumberOfVirteces, OrigCost, Path,
  114.          DuplicatePath);
  115.    /* Calculate and print initial solution - reversed starting circuit */
  116.       fprintf(fp, "\014\n          ");
  117.       fprintf(fp, "T R A V E L I N G   S A L E S M A N   P R O B L E M");
  118.       fprintf(fp, "\n\n\n%u city problem continued:", NumberOfVirteces);
  119.       fprintf(fp, " (reversed nearest neighbor circuit)\n\n\n");
  120.       Path2 = DuplicatePath->prior;
  121.       for ( index = 1; index <= NumberOfVirteces; index++) {
  122.          Path->position = Path2->position;
  123.          Path = Path->next;
  124.          Path2 = Path2->prior;
  125.       }
  126.       Path2 = DuplicatePath;
  127.       for ( index = 1; index <= NumberOfVirteces; index++) {
  128.          Path2->position = Path->position;
  129.          Path = Path->next;
  130.          Path2 = Path2->next;
  131.       }
  132.       fprintf(fp, "Reverse Nearest Neighbor solution: \n\n");
  133.       fprintf(fp, "   A circuit with cost %ld", CircuitCost);
  134.       fprintf(fp, " was found in %ld", TotalTime);
  135.       fprintf(fp, " ticks with the following path:\n   ");
  136.       PrintCircuit (fp, NumberOfVirteces, Path);
  137.       fprintf(fp, "\n\n\n");
  138.       CalculateImprovements (fp, NumberOfVirteces, OrigCost, Path,
  139.          DuplicatePath);
  140.    /* Calculate and print initial solution - poor starting circuit */
  141.       fprintf(fp, "\014\n          ");
  142.       fprintf(fp, "T R A V E L I N G   S A L E S M A N   P R O B L E M");
  143.       fprintf(fp, "\n\n\n%u city problem continued:", NumberOfVirteces);
  144.       fprintf(fp, " (poor starting circuit)\n\n\n");
  145.       printf("\n   Farthest Neighbor calculation ... ");
  146.       StartTime = GetTime ();
  147.       CircuitCost = FarNeighbor (NumberOfVirteces, Path);
  148.       TotalTime = ElapsedTime (StartTime);
  149.       printf("%ld ticks.", TotalTime);
  150.       fprintf(fp, "Farthest Neighbor solution: \n\n");
  151.       fprintf(fp, "   A circuit with cost %ld", CircuitCost);
  152.       fprintf(fp, " was found in %ld", TotalTime);
  153.       fprintf(fp, " ticks with the following path:\n   ");
  154.       PrintCircuit (fp, NumberOfVirteces, Path);
  155.       fprintf(fp, "\n\n\n");
  156.       OrigCost = CircuitCost;
  157.       Path2 = DuplicatePath;
  158.       for ( index = 1; index <= NumberOfVirteces; index++) {
  159.          Path2->position = Path->position;
  160.          Path = Path->next;
  161.          Path2 = Path2->next;
  162.       }
  163.       CalculateImprovements (fp, NumberOfVirteces, OrigCost, Path,
  164.          DuplicatePath);
  165.    /* Clean up and go */
  166.       fclose (fp);
  167.       Terminate (0, "      Execution Terminated Normally!");
  168. } /* TravelingSalesman - main */
  169.  
  170.  
  171. Terminate (code, message)
  172.    int code;
  173.    char *message;
  174. {
  175.    printf("\n*******************************************");
  176.    printf("\n %s", message);
  177.    printf("\n*******************************************\n\n\007");
  178.    exit(code);
  179. } /* Terminate */
  180.  
  181.  
  182. PrintCircuit (fp, NumberOfVirteces, Path)
  183.    FILE *fp;
  184.    unsigned NumberOfVirteces;
  185.    NODE *Path;
  186. {
  187.    unsigned count, index;
  188.  
  189.       count = 0;
  190.       for ( index = 1; index <= NumberOfVirteces; index++) {
  191.          if (count >= 18) {
  192.             fprintf(fp, "\n    ");
  193.             count = 1;
  194.          } else {
  195.             count++;
  196.          }
  197.          fprintf(fp, "-%u-", Path->position);
  198.          Path = Path->next;
  199.       }
  200. } /* PrintCircuit */
  201.  
  202.  
  203. CalculateImprovements (fp, NumberOfVirteces, OrigCost, Path, DuplicatePath)
  204.    FILE *fp;
  205.    unsigned NumberOfVirteces;
  206.    long OrigCost;
  207.    NODE *Path, *DuplicatePath;
  208. {
  209.    NODE *Path2;
  210.    unsigned index;
  211.    long CircuitCost, StartTime, TotalTime;
  212.  
  213.       Path2 = DuplicatePath;
  214.       for ( index = 1; index <= NumberOfVirteces; index++) {
  215.          Path->position = Path2->position;
  216.          Path = Path->next;
  217.          Path2 = Path2->next;
  218.       }
  219.    /* Calculate and print improved solution */
  220.       printf("\n   PointOpt calculation ... ");
  221.       StartTime = GetTime ();
  222.       CircuitCost = PointOpt (NumberOfVirteces, Path);
  223.       TotalTime = ElapsedTime (StartTime);
  224.       printf("%ld ticks.", TotalTime);
  225.       fprintf(fp, "PointOpt improvement: \n\n");
  226.       if (OrigCost > CircuitCost) {
  227.          PrintImprovement (fp, NumberOfVirteces, CircuitCost, OrigCost,
  228.             TotalTime, Path);
  229.       } else {
  230.          fprintf(fp, "   No improvement.    %ld ticks\n\n\n", TotalTime);
  231.       }
  232.       Path2 = DuplicatePath;
  233.       for ( index = 1; index <= NumberOfVirteces; index++) {
  234.          Path->position = Path2->position;
  235.          Path = Path->next;
  236.          Path2 = Path2->next;
  237.       }
  238.    /* Calculate and print improved solution */
  239.       printf("\n   TwoOpt calculation ... ");
  240.       StartTime = GetTime ();
  241.       CircuitCost = TwoOpt (NumberOfVirteces, Path);
  242.       TotalTime = ElapsedTime (StartTime);
  243.       printf("%ld ticks.", TotalTime);
  244.       fprintf(fp, "TwoOpt improvement: \n\n");
  245.       if (OrigCost > CircuitCost) {
  246.          PrintImprovement (fp, NumberOfVirteces, CircuitCost, OrigCost,
  247.             TotalTime, Path);
  248.       } else {
  249.          fprintf(fp, "   No improvement.    %ld ticks\n\n\n", TotalTime);
  250.       }
  251.       Path2 = DuplicatePath;
  252.       for ( index = 1; index <= NumberOfVirteces; index++) {
  253.          Path->position = Path2->position;
  254.          Path = Path->next;
  255.          Path2 = Path2->next;
  256.       }
  257.    /* Calculate and print improved solution */
  258.       printf("\n   Hybrid calculation ... ");
  259.       StartTime = GetTime ();
  260.       CircuitCost = Hybrid (NumberOfVirteces, Path);
  261.       TotalTime = ElapsedTime (StartTime);
  262.       printf("%ld ticks.", TotalTime);
  263.       fprintf(fp, "Hybrid improvement: \n\n");
  264.       if (OrigCost > CircuitCost) {
  265.          PrintImprovement (fp, NumberOfVirteces, CircuitCost, OrigCost,
  266.             TotalTime, Path);
  267.       } else {
  268.          fprintf(fp, "   No improvement.    %ld ticks\n\n\n", TotalTime);
  269.       }
  270.       Path2 = DuplicatePath;
  271.       for ( index = 1; index <= NumberOfVirteces; index++) {
  272.          Path->position = Path2->position;
  273.          Path = Path->next;
  274.          Path2 = Path2->next;
  275.       }
  276.    /* Calculate and print improved solution */
  277.       printf("\n   3-Opt calculation ... ");
  278.       StartTime = GetTime ();
  279.       CircuitCost = ThreeOpt (NumberOfVirteces, Path);
  280.       TotalTime = ElapsedTime (StartTime);
  281.       printf("%ld ticks.\n\n", TotalTime);
  282.       fprintf(fp, "3-Opt improvement: \n\n");
  283.       if (OrigCost > CircuitCost) {
  284.          PrintImprovement (fp, NumberOfVirteces, CircuitCost, OrigCost,
  285.             TotalTime, Path);
  286.       } else {
  287.          fprintf(fp, "   No improvement.   %ld ticks\n\n\n", TotalTime);
  288.       }
  289. } /* CalculateImprovements */
  290.  
  291.  
  292. PrintImprovement (fp, NumberOfVirteces, CircuitCost, OrigCost,
  293.                                                    TotalTime, Path)
  294.    FILE *fp;
  295.    unsigned NumberOfVirteces;
  296.    long CircuitCost, OrigCost;
  297.    long TotalTime;
  298.    NODE *Path;
  299. {
  300.  
  301.    fprintf(fp, "   A circuit with cost %ld", CircuitCost);
  302.    fprintf(fp, " was found in %ld", TotalTime);
  303.    fprintf(fp, " ticks with the following path:\n   ");
  304.    PrintCircuit (fp, NumberOfVirteces, Path);
  305.    fprintf(fp, "\n   This solution represents an improvement of ");
  306.    fprintf(fp, "%ld over the initial solution.\n\n\n", (OrigCost - CircuitCost));
  307. } /* PrintImprovement */
  308.